首页 > 试题广场 >

用两个栈实现队列

[编程题]用两个栈实现队列

热度指数：1010174 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

用两个栈来实现一个队列，使用n个元素来完成 n 次在队列尾部插入整数(push)和n次在队列头部删除整数(pop)的功能。队列中的元素为int类型。保证操作合法，即保证pop操作时队列内已有元素。

数据范围： $n\le1000$

要求：存储n个元素的空间复杂度为 $O(n)$ ，插入与删除的时间复杂度都是 $O(1)$

示例1

输入

["PSH1","PSH2","POP","POP"]

输出

1,2

说明

"PSH1":代表将1插入队列尾部
"PSH2":代表将2插入队列尾部
"POP“:代表删除一个元素，先进先出=>返回1
"POP“:代表删除一个元素，先进先出=>返回2

示例2

输入

["PSH2","POP","PSH1","POP"]

输出

2,1

算法知识视频讲解

查看答案及解析

推荐

张佃鹏

class Solution
{
public:
    void push(int node) {
       stack1.push(node); 
    }

    int pop() {
        int a;
        if(stack2.empty()){
            while(!stack1.empty()){
                a=stack1.top();
                stack2.push(a);
                stack1.pop();
            }
        }
        a=stack2.top();
        stack2.pop();
        return a;
        
    }

private:
    stack<int> stack1;
    stack<int> stack2;
};

用两个栈实现一个队列的功能?要求给出算法和思路!

<分析>：

入队：将元素进栈A

出队：判断栈B是否为空，如果为空，则将栈A中所有元素pop，并push进栈B，栈B出栈；

如果不为空，栈B直接出栈。

用两个队列实现一个栈的功能?要求给出算法和思路!

<分析>：

入栈：将元素进队列A

出栈：判断队列A中元素的个数是否为1，如果等于1，则出队列，否则将队列A中的元素以此出队列并放入队列B，直到队列A中的元素留下一个，然后队列A出队列，再把队列B中的元素出队列以此放入队列A中。

编辑于 2015-08-18 23:15:03 回复(73)

Python 3

匿名牛由

# -*- coding:utf-8 -*-
class Solution:

    # stack1是输入栈，stack2是输出栈
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    
    def push(self, node):
        self.stack1.append(node)
        # write code here
    
    def pop(self):
        tmp = self.stack1[0]
        del self.stack1[0]
        return tmp

py：我可以一个栈实现队列/狗头

发表于 2023-03-12 20:41:46 回复(0)

Python 3

牛客819077096号

我一开始还想的比较复杂，就是我以为你每次出栈操作还得入栈的数据进行清空，事实上这里不需要

发表于 2022-12-01 12:59:21 回复(0)

Python 3

任逍遥a

不明白官方的思路中，pop时放到stack2的元素还在再放回stack1中，每次优先从stack2出栈，stack2为空时从stack1出栈到stack2中，试了下，官方代码78ms，我的49ms，就是内存稍多了点

发表于 2022-10-04 20:48:31 回复(0)

Python 3

JianYue

# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
    def pop(self):
        if len(self.stack2) > 0:
            return self.stack2.pop(0)
        while len(self.stack1) > 0:
            n = self.stack1.pop(0)
            self.stack2.append(n)
        return self.stack2.pop(0)

发表于 2022-09-14 11:02:33 回复(0)

Python 3

lambday

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if not self.stack1 and not self.stack2:
            return None
        if self.stack2:
            return self.stack2.pop()
        while self.stack1:
            cur = self.stack1.pop()
            self.stack2.append(cur)
        
        return self.stack2.pop()

发表于 2022-08-02 15:26:04 回复(0)

Python 3

风软一江山

#栈1用来进栈，出栈时如果栈2为空则栈1元素全进栈2再出一个栈顶元素，如果栈2不为空则直接出栈顶元素
# -*- coding:utf-8 -*-
class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2022-07-29 12:33:36 回复(0)

Python 3

来牛客玩玩

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
        
    def push(self, node):
        # write code here
        self.stack1.append(node)
        
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2022-07-09 17:21:54 回复(0)

Python 3

Vivimore

class Solution:
    def __init__(self):
        self.s1 = []
        self.s2 = []
    def push(self, node):
        self.s1.append(node)
    def pop(self):
        if not self.s2:
            while self.s1:
                self.s2.append(self.s1.pop())
        return self.s2.pop()

发表于 2022-05-17 16:28:07 回复(0)

Python 3

牛客568079703号

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        if not self.stack2:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2022-04-29 13:53:42 回复(0)

Python 3

danspace

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        # write code here
        self.stack1.append(node)
    def pop(self):
        # return xx
        return self.stack1.pop(0)

发表于 2022-04-19 15:06:36 回复(0)

Python 3

想起来就做两道（JihongRen）

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []

    def push(self, node):
        self.stack1.append(node)

    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            
            return self.stack2.pop()

发表于 2022-03-10 15:03:08 回复(0)

Python 3

JSFaner

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
        
    def pop(self):
        if not self.stack1 and not self.stack2: return None
        if not self.stack2:
            for i in range(len(self.stack1)):
                self.stack2.append(self.stack1.pop())
        return self.stack2.pop()

发表于 2022-01-04 22:28:12 回复(0)

Python 3

Joy_9

class Solution:
    def __init__(self):
        self.stack1 = []
        self.stack2 = []
    def push(self, node):
        self.stack1.append(node)
        # write code here
    def pop(self):
        if self.stack2:
            return self.stack2.pop()
        elif not self.stack1:
            return
        else:
            while self.stack1:
                self.stack2.append(self.stack1.pop())
            return self.stack2.pop()

发表于 2022-01-04 01:41:40 回复(0)

Python 3

苏科大亮仔

# -*- coding:utf-8 -*-
class Solution:
def __init__(self):
self.stack1 = []
self.stack2 = []
def push(self, node):
self.stack1.append(node)
self.stack2 = list(reversed(self.stack1))
# write code here
def pop(self):
# return xx
pp = self.stack2.pop(-1)
self.stack1 = list(reversed(self.stack2))
return pp

发表于 2021-12-22 13:39:35 回复(0)